min属性 潜水员
题目 潜水员
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：一个为氧气，一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的 最低限度 的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的 最低值。
输入格式
第一行有2个整数 m，n。它们表示氧，氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
1≤m≤21,1≤n≤79,1≤k≤1000,1≤ai≤21,1≤bi≤79,1≤ci≤800
输入样例：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例：
249
思路分析
不难发现也是一个二维限制问题 但属性有些不同
- 普通的二维背包费用问题 f(i,j,k) 表示从前i个物品中选，且花费1不超过j,花费2不超过k的 最大 价值
- 潜水员 f(i,j,k) 表示从前i个物品中选，且花费1不少于j,花费2不少于k的 最小 价值
f[i][j][k]，表示从前i个气缸中选取一些气缸，恰好满足至少有j升氧气和k升氮气的情况下，气缸的最小总重量
初始化
dp[0][0][0] = 0：不选取任何气缸时，没有重量，也没有氧气和氮气。- 其他情况初始化为一个大数，例如
INT_MAX，表示在没有选择任何气缸的情况下，不可能满足任何正的氧气或氮气需求。
这样分析完 似乎与普通的二维费用背包没有区别 不可能，必然是遗漏了些什么
考虑j−v1<0,k−v2<0的情况
有普通的二维费用背包问题中，j,k是不能进行超载的，超过了背包就太重， 背包就 漏 了！
在本题中，是 可以超载 的，理解一下超载是什么意思：
j:氧气还需缺少j升
k:氮气还需缺少k升
例如：j=2,k=5,就是氧气还需要2升，氮气还需要5升，现在出现的某个气瓶，氧气20升，氮气50升，一个就可以把你的需求满足，那么：你还需要氧气多少升、氮气多少升？ 答：不需要，都可以满足要求了，即j=0,k=0,也就是f[i−1][0][0]+w,而对于一个无欲无求的f[i−1][0][0]自然是等于0,也就是f[i][j][k]=w
状态转移方程
对于每一个气缸i（其中i从1到k），我们可以选择它或者不选择它。如果我们选择这个气缸，那么对于每个j（氧气需求）和k（氮气需求），状态转移方程如下：
dp[i][j][k]=min(dp[i−1][j][k],dp[i−1][max(j−ai,0)][max(k−bi,0)]+ci)
dp[i-1][j][k]：不选择当前气缸的情况。dp[i-1][max(j-ai, 0)][max(k-bi, 0)] + ci：选择当前气缸的情况，其中ai、bi和ci分别是当前气缸提供的氧气量、氮气量和重量。我们从j和k中减去当前气缸提供的量（如果j-ai或k-bi计算出来是负数，将需求量设置为0，因此用max保证至少为0），然后加上当前气缸的重量。
目标
遍历完成后，dp[k][m][n]（其中k是气缸的总数，m和n分别是所需的氧气和氮气量）就是所求的最小重量。如果某些状态无法通过选择气缸来满足氧气和氮气的需求，那么它们的值会保持为初始化的大数，这些状态不会影响最终结果。
为什么以max为属性的背包问题不需要做max(j-v,0) 而 以min为属性要考虑呢
最大化属性（Max属性）
在最大化属性的问题中，我们通常关注的是如何通过选择一系列物品来最大化总价值。这里的约束是背包的容量限制。
-
目标和约束：我们希望在不超过背包容量的前提下，尽可能地增加背包中物品的总价值。
-
处理
j-v<0的情况：如果当前物品的体积v大于当前考虑的容量j（即j-v<0），则这个物品无法被选入背包，因为它单独就超过了背包的容量限制。在最大化问题中，这意味着对于任何超过背包容量的物品，我们简单地不选择它。这是一个直接的决策，因为选择它会违反背包容量的基本约束。我们在一开始就做了这件事——if(体积足够） 才考虑右边集合的情况 直接排除了 而无需考虑什么小于0再取0
最小化属性（Min属性）
在最小化属性的问题中，如寻找满足特定需求（比如特定量的氧气和氮气）的最小总重量，问题的性质和处理方式有所不同。
- 目标和约束：我们需要精确满足一些外部给定的条件（例如，氧气和氮气的特定需求），同时尽可能地减少满足这些条件所需的总重量。
- 处理
j-v<0的情况：在最小化属性的问题中，j-v<0的处理更复杂。我们需要确保所有需求都被精确满足，这可能包括对不同物品组合的详细考虑。对于某些需求，可能不存在任何单个物品可以满足的情况，因此我们需要考虑组合物品以满足需求。在这种情况下，即使某些物品组合的部分属性（如氧气或氮气的量）超过了需求，我们也可能需要选择它们，因为这可能导致总重量的最小化。
核心差异
- 最大化问题：不需要特别处理
j-v<0的情况，因为超出容量的物品自然被排除，不会对最大化目标产生贡献。 - 最小化问题：需要详细考虑各种情况，包括
j-v<0，因为我们的目标是找到满足特定需求的最轻重量组合，这可能涉及到对各种物品组合的仔细评估，即使某些物品单独看似不可行。
总的来说，最大化和最小化属性的背包问题在处理j-v<0的情况时有本质的不同，这反映了问题目标和约束条件对问题解法的影响。最大化问题简化了决策过程，因为只有在不违反容量限制的情况下才考虑增加价值。而最小化问题则需要更多地考虑如何精确满足给定的需求，即使这意味着要考虑在某些情况下似乎不可行的物品组合。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 110;
int f[N][M][M];
int n, m1, m2;
//二维费用01背包-不少于维度费用，求最小代价
int main() {
scanf("%d %d %d", &m1, &m2, &n);
//求最小值 价值不小于 把[0][0][0]初始化成0 其他正无穷
memset(f, 0x3f, sizeof f);
f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
int v1, v2, w;
scanf("%d %d %d", &v1, &v2, &w);// 输入每个气缸的氧气量，氮气量和重量
for (int j = 0; j <= m1; j++)
for (int k = 0; k <= m2; k++) {
f[i][j][k] = f[i - 1][j][k];// 不选择当前气缸
// 选择当前气缸
f[i][j][k] = min(f[i][j][k], f[i-1][max(0, j - v1)][max(0, k - v2)] + w); // 选择当前气缸
}
}
printf("%d\n", f[n][m1][m2]);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 22, M = 80;
int n, m, K;
int f[N][M];
int main() {
cin >> n >> m >> K;
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
while (K--) {
int v1, v2, w;
cin >> v1 >> v2 >> w;
for (int i = n; i >= 0; i--)
for (int j = m; j >= 0; j--)
f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
}
cout << f[n][m] << endl;
return 0;
}
💬 评论